/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package open.algo.sort;

/**
 *
 * @author lee
 */
public class MergeSort implements Sort
{

    /**
     * 1,2,3, 5, 6, 7
     *
     * 0 1 2  3 4 5
     *
     * @param a
     * @param s1
     * @param s2
     */
    public void merge(int[] a, int s1, int step)
    {
        int s2 = s1 + step;
        int e2 = s2 + step < a.length ? s2 + step : a.length;

        if (s2 >= a.length || a[s2 -1] < a[s2])
        {
            return;
        }

        int temp = 0;
        while (s1 < s2 && s2 < e2)
        {
            if (a[s1] < a[s2])
            {
                s1++;
            } else
            {
                temp = a[s2];
                for (int i = s2;  i > s1; i--)
                {
                    a[i] = a[i - 1];
                }
                a[s1] = temp;
                s2++;
                s1++;
            }
        }
    }

    /**
     * 0, 1, 2, 3
     * @param a
     */
    @Override
    public void sort(int[] a)
    {
        int step = 1;
        while (step < a.length)
        {
            for (int i = 0; i < a.length; i += step * 2)
            {
                merge(a, i, step);
            }

            step = step << 1;
        }
    }

    public static void main(String[] args)
    {
        SortTest test = new SortTest();
        int[] a = test.getArray();
        SortTest.print(a);
        Sort sort = new MergeSort();
        sort.sort(a);
        SortTest.print(a);
    }
}
